package com.atguigui.leetcode;

/**
 * 813.最大平均值和的分组
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/11/28 8:52
 */
public class P813LargestSumOfAverages {
    public static void main(String[] args) {
        Solution solution = new P813LargestSumOfAverages().new Solution();
        // TO TEST
    }

    class Solution {
        public double largestSumOfAverages(int[] nums, int k) {
            int n = nums.length;
            double[] prefix = new double[n + 1];
            //初始化，把数组切分成n个单独的
            for (int i = 0; i < n; i++) {
                prefix[i + 1] = prefix[i] + nums[i];
            }
            double[][] dp = new double[n + 1][k + 1];
            for (int i = 1; i <= n; i++) {
                dp[i][1] = prefix[i] / i;
            }
            for (int j = 2; j <= k; j++) {
                for (int i = j; i <= n; i++) {
                    for (int x = j - 1; x < i; x++) {
                        dp[i][j] = Math.max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
                    }
                }
            }
            return dp[n][k];
        }
    }
}
